package org.lql.algo.codecrush.hot100.dynamicProgramming;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author: liangqinglong
 * @date: 2025-09-14 15:05
 * @description: 139. 单词拆分 <a href="https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class WordBreak {

	public boolean wordBreak(String s, List<String> wordDict) {
		Set<String> set = new HashSet<>(wordDict);
		// dp[i] 表示字符串 s 从开始到索引 i-1 的子字符串是否可以被拆分。
		boolean[] dp = new boolean[s.length() + 1];
		dp[0] = true;
		for (int i = 1; i <= s.length(); i++) {
			// 从当前位置向前遍历，寻找可能的拼接方式
			for (int j = 0; j < i; j++) {
				// 如果到 j 的位置可以被拼接，并且 j 到 i 的子串也在字典中，则当前位置 i 可以被拼接
				if (dp[j] && set.contains(s.substring(j, i))) {
					dp[i] = true;
					break;
				}
			}
		}
		return dp[s.length()];
	}
}
